{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Thinking Recursively"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And, oh, by the way, I hate having those closing parens jump into existence automatically. Let's turn them off!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the file `~/.jupyter/custom/custom.js`, add these lines:\n",
    "\n",
    "```javascript\n",
    "require(['notebook/js/codecell'], function (codecell) {\n",
    "        codecell.CodeCell.options_default.cm_config.autoCloseBrackets = false;\n",
    "        });\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "\n",
       "IPython.CodeCell.options_default.cm_config.autoCloseBrackets = false;"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%javascript\n",
    "\n",
    "IPython.CodeCell.options_default.cm_config.autoCloseBrackets = false;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Example: member"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define my-member\n",
    "  (lambda (item lyst)\n",
    "    (cond\n",
    "     ((null? lyst) #f)\n",
    "     ((eq? item (car lyst)) #t)\n",
    "     (else (my-member item (cdr lyst))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'a '()) ;; -> #f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'a '(a)) ;; -> #t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'a '(a b c)) ;; -> #t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'c '(a b c)) ;; -> #t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'd '(a b c)) ;; -> #f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-member 'b '(a (b) c)) ;; -> #f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 Example: length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define my-length\n",
    "  (lambda (lyst)\n",
    "    (cond\n",
    "     ((null? lyst) 0)\n",
    "     (#t (+ 1 (my-length (cdr lyst)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-length '()) ;; -> 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-length '(100)) ;; -> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-length '(100 (200) 300)) ;; -> 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Example: sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define my-sum\n",
    "  (lambda (lyst)\n",
    "    (cond\n",
    "     [(null? lyst) 0]\n",
    "     [else (+ (car lyst) \n",
    "              (my-sum (cdr lyst)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-sum '()) ;; -> 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-sum '(23)) ;; -> 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(my-sum '(1 2 3)) ;; -> 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\n",
      "Traceback (most recent call last):\n",
      "  File \"In [25]\", line 1, col 1, in 'my-sum'\n",
      "  File \"In [18]\", line 6, col 15, in 'my-sum'\n",
      "  File \"In [18]\", line 6, col 15, in 'my-sum'\n",
      "  File \"In [18]\", line 6, col 15, in 'my-sum'\n",
      "  File \"In [18]\", line 5, col 12, in '+'\n",
      "UnhandledException: unsupported operand type(s) for +: 'int' and 'cons'\n",
      "\n",
      "\u001b[0m"
     ]
    }
   ],
   "source": [
    "(my-sum '(1 2 3 (4 (5) 6) 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 Example: sum*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(define sum*\n",
    "  (trace-lambda \"sum*\" (lyst)\n",
    "    (cond\n",
    "     [(null? lyst) 0]\n",
    "     [(list? (car lyst)) (+ (sum* (car lyst))\n",
    "                            (sum* (cdr lyst)))]\n",
    "     [else (+ (car lyst) \n",
    "              (sum* (cdr lyst)))])))     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "call: (\"sum*\" (1 2 3 (4 (5) 6) 7))\n",
      "call: (\"sum*\" (2 3 (4 (5) 6) 7))\n",
      "call: (\"sum*\" (3 (4 (5) 6) 7))\n",
      "call: (\"sum*\" ((4 (5) 6) 7))\n",
      "call: (\"sum*\" (4 (5) 6))\n",
      "call: (\"sum*\" ((5) 6))\n",
      "call: (\"sum*\" (5))\n",
      "call: (\"sum*\" ())\n",
      "return: 0\n",
      "return: 5\n",
      "call: (\"sum*\" (6))\n",
      "call: (\"sum*\" ())\n",
      "return: 0\n",
      "return: 6\n",
      "return: 11\n",
      "return: 15\n",
      "call: (\"sum*\" (7))\n",
      "call: (\"sum*\" ())\n",
      "return: 0\n",
      "return: 7\n",
      "return: 22\n",
      "return: 25\n",
      "return: 27\n",
      "return: 28\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(sum* '(1 2 3 (4 (5) 6) 7)) ;; -> 28"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 3",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}